<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>最小子串</title>
  </head>
  <body>
    <script>
      /**
       * @param {string} s
       * @param {string} t
       * @return {string}
       */
      var minWindow = function (s, t) {
        // 统计 t 字符串的每个字符的数量
        const targetMap = countMap(t);
        console.log('targetMap----', targetMap)

        let sl = s.length;
        let tl = t.length;
        let left = 0; // 左指针
        let right = -1; // 右指针
        let min = ""; // 最小子串
        let windowMap = {}; // 窗口中字符统计为 map 格式

        // 两种情况会跳出循环：1.left > sl - tl  2.right > sl
        while (left <= sl - tl && right < sl) {
          let isInclude = true; // 滑动窗口是否包含子串 t

          // 统计，对比 targetMap 和 windowMap。判断滑动窗口是否包含子串 t
          Object.keys(targetMap).forEach((k) => {
            const num = targetMap[k];
            const winNum = windowMap[k];
            if (!winNum || winNum < num) {
              isInclude = false;
            }
          });

          if (isInclude) {
            // 记录当前字符串为 min
            const iLength = right - left + 1;
            if (iLength < min.length || min === "") {
              min = s.substring(left, right + 1); // substring(startIndex, endIndex) 包含 startIndex，不包含 endIndex
            }
            // 右移左指针，进一步缩小窗口
            windowMap[s[left]]--;
            left++;
          } else {
            // 右移右指针，扩大窗口
            if (windowMap[s[right + 1]]) {
              windowMap[s[right + 1]]++;
            } else {
              windowMap[s[right + 1]] = 1;
            }
            right++;
          }
        }
        return min;
      };

      function countMap(str) {
        let map = {};
        for (let i = 0; i < str.length; i++) {
          const letter = str[i]
          if (map[letter]) {
            map[letter]++
          } else {
            map[letter] = 1;
          }
        }
        return map;
      }

      const result = minWindow('ADOBECODEBANC', 'ABC')
      console.log(result)
    </script>
  </body>
</html>
